package com.explorati.LeetCode88.mergesortarray;

import java.util.Arrays;

/**
 * 88. Merge Sorted Array
 * 
 * Input: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3
 * 
 * Output: [1,2,2,3,5,6]
 * 
 * @author explorati
 *
 */
public class Solution {
	public static int[] merge(int[] nums1, int m, int[] nums2, int n) {
		// 数组拷贝
		// int[] arr = new int[m + n];
		// int i = 0;
		// int j = m, k = n;
		// int start = 0;
		// int mid = m;
		// while (m != 0) {
		// arr[i] = nums1[i];
		// i++;
		// m--;
		// }
		// while (n != 0) {
		// arr[i] = nums2[i - j];
		// i++;
		// n--;
		// }

		// 数组拷贝
		int[] arr = Arrays.copyOf(nums1, nums1.length);
		int c = 0;
		for (int d = m; d < nums1.length; d++) {
			arr[d] = nums2[c];
			c++;
		}

		int i = 0;
		int j = m;

		// 遍历拷贝的数组并将其比较之后的值放入nums1
		for (int a = 0; a < arr.length; a++) {
			if (i >= m) {
				nums1[a] = arr[j];
				j++;
			} else if (j >= nums1.length) {
				nums1[a] = arr[i];
				i++;
			} else if (arr[j] > arr[i]) {
				nums1[a] = arr[i];
				i++;
			} else if (arr[j] <= arr[i]) {
				nums1[a] = arr[j];
				j++;
			}
		}

		return nums1;
	}

	public static void main(String[] args) {
		int[] nums1 = { 1, 2, 3, 0, 0, 0 };
		int[] nums2 = { 4, 5, 6 };
		int[] arr = merge(nums1, 3, nums2, 3);

		// int[] arr = merge(nums1, 3, nums2, 3);
		for (int i : arr) {
			System.out.print(i + " ");
		}

	}
}
